/*************************************************************************
	> File Name: merge_list.cpp
	> Author: 
	> Mail: 
	> Created Time: 二 10/13 12:48:12 2015
 ************************************************************************/

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

int arr[100000] = {0};
int Link[100000] = {0};
/******************************
 * 归并链接表排序
 * ****************************/

void MergeL(int, int, int&);

void MergeSortL(int low, int high, int &p) {
    if (low == high) {
        p = low;
    }
    else if (low < high){
        int q = 0;
        int r = 0;
        int mid = (low + high) / 2;
        MergeSortL(low, mid, q);
        MergeSortL(mid + 1, high, r);
        MergeL(q,r,p);
    }
}

void MergeL(int q, int r, int &p) {
    int i, j, k;
    i = q;
    j = r;
    k = 0;
    while ( (i != 0) && (j != 0) ) {
        if (arr[i] <= arr[j]) {
            Link[k] = i;
            k = i;
            i = Link[i];

        }
        else {
            Link[k] = j;
            k = j;
            j = Link[j];
        }
    }
    if (i == 0)
        Link[k] = j;
    if (j == 0)
        Link[k] = i;
    p = Link[0];
}

/******************************
 * 归并排序
 * ****************************/
 void Merge(int a[], int b[], int low, int mid, int high) {
     int k = 0;
     int i = low;
     int j = mid + 1;
     while ( (i <= mid) && (j <= high) ) {
         if (a[i] <= a[j])
            b[k++] = a[i++];
         else
            b[k++] = a[j++];
     }
     if (i > mid) {
         while (j <= high)
            b[k++] = a[j++];
     }
     else {
         while (i <= mid)
            b[k++] = a[i++];
     }
     for (int m = 0; m < k; ++m) {
         a[low++] = b[m];
     }
 }
 void MergeSort(int a[], int b[], int low, int high) {
     if (low < high) {
         int mid = (low + high) / 2;
         MergeSort(a, b, low, mid);
         MergeSort(a, b, mid + 1, high);
         Merge(a, b, low, mid, high);
     }
 }
/******************************
 * 快速排序
 * ****************************/

void Qsort(int *a, int low, int high) {
    if (low >= high) {

    }
    else {
        int i, j;
        int tmp = a[low];
        i = low;
        j = high;
        int partition = 0;
        while (i < j) {
            while ( (a[i] <= tmp) && (i < j)) {
                ++i;
            }
            while (a[j] > tmp) {
                --j;
            }    //不能有等于号，比如［5，5，5］，如果有等于号，则会发生数组越界
            if (i < j) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        a[low] = a[j];
        a[j] = tmp;
        partition = j;
        Qsort(a, low, partition-1);
        Qsort(a, partition+1, high);
    }
}


int main(void) {
    srand(time(NULL));
    for (int m = 1; m < 100000; ++m) {
        arr[m] = rand() % 100000;
    }
    int arr1[100000];
    int arr2[100000];
    int arr3[100000]; //临时数组
    for (int m = 0; m < 99999; ++m) {
        arr1[m] = arr[m+1];
        arr2[m] = arr[m+1];
    }
    int p = 0;
    clock_t t1 = clock();
    MergeSortL(1, 99999, p);
    clock_t t2 = clock();
    cout << "the time MergeSortL is:" << (double)(t2 - t1)/CLOCKS_PER_SEC * 1000 << "ms" << endl;
    
    clock_t t3 = clock();
    MergeSort(arr2, arr3, 0, 99998);
    clock_t t4 = clock();
    cout << "the time MergeSort is:" << (double)(t4 - t3)/CLOCKS_PER_SEC * 1000 << "ms" << endl;

    int i = 0;
    clock_t t5 = clock();
    cout << endl;
    Qsort(arr1, 0, 99998);
    clock_t t6 = clock();
    cout << "the time Qsort is:" << (double)(t6 - t5)/CLOCKS_PER_SEC * 1000 << "ms" << endl;
    cout << "RAND_MAX:" << RAND_MAX << endl;
    cout << "CLOCKS_PER_SECOND:" << CLOCKS_PER_SEC << endl;

    int n = 0;
    while (n < 99999 && arr[Link[i]] == arr1[n] && arr1[n] == arr2[n]) {
        ++n;
        i = Link[i];
    }
    if (n == 99999)
        cout << "排序结果一样" << endl;

    return 0;
}
